/*
 * @Description: 字典树竞赛实现
 * @Autor: yanwang
 * @Date: 2021-11-05 16:01:03
 * @LastEditors: yanwang
 * @LastEditTime: 2021-11-09 15:44:18
 */
class Node {
  constructor(base = 26) {
    this.base = base;
    this.flag = 0;
    // 存储子节点在 trie 中的的地址（下标）
    this.next = new Array(base).fill(0);
  }
  clear() {
    this.flag = 0;
    for (let i = 0; i < this.base.length; i++) {
      this.next[i] = 0;
    }
  }
}

class Trie {
  constructor() {
    this.BASE = 26;  // 假设字典树中只有26个小写英文字母
    this.clearTrie();
  }

  // 初始化 trie
  clearTrie() {
    this.root = 1;
    this.cnt = 2; // 新节点的地址（下标）
    this.trie = []; // 存储所有节点

    this.trie[this.root] = new Node();
  }

  // 创建新节点
  __getNewNode() {
    this.trie[this.cnt] = new Node();
    return this.cnt++; // 后++
  }

  // 插入字符串， 没有标记是否第一次插入
  insert(word) {
    let p = this.root; // 根节点下标
    for (let i = 0; i < word.length; i++) {
      const x = word[i];
      const ind = x.charCodeAt() - 'a'.charCodeAt(); // 获取次字母存放在哪条边上

      // 从根节点开始向下找， 将对应边上放置节点
      if(this.trie[p].next[ind] === 0) this.trie[p].next[ind] = this.__getNewNode();
      p = this.trie[p].next[ind];
    }

    if(this.trie[p].flag === 1) return false; // 非首次插入
    // 字符串插入完毕，最后一个节点改为红色
    this.trie[p].flag = 1;
    return true;
  }
  
  // 返回是否搜索到
  search(word) {
    let p = this.root;
    for (let i = 0; i < word.length; i++) {
      const x = word[i];
      const ind = x.charCodeAt() - 'a'.charCodeAt(); // 如果存在，应该在第几条边上

      // 向下查找
      p = this.trie[p].next[ind]; // this.trie[p].next: 根节点p 的所有子节点
      if(p === 0) return false;
    }
    return this.trie[p].flag === 1;
  }


  // 输出所有字符串
  output() {
    let ret = [];
    this.__output(this.root, '', ret);
    return ret;
  }
  __output(root, s, ret) {
    if(root === 0) return;
    if(this.trie[root].flag === 1) ret.push(s);

    for(let i = 0; i < this.BASE; i++) {
      this.__output(this.trie[root].next[i], s + String.fromCharCode('a'.charCodeAt() + i), ret);
    }
  }
  
}

function test() {
  let trie = new Trie();
  let res;
  res = trie.insert('hello');
  // console.log(res);
  res = trie.insert('world');
  // console.log(res);
  res = trie.insert('world');
  // console.log(res);
  res = trie.search('hello');
  // console.log(res);
  res = trie.search('hell');
  // console.log(res);
  res = trie.search('world');
  // console.log(res);
  let ret = trie.output();
  console.log(ret);
}
test();
